Estimating the density of a distribution from samples is a fundamental problem in statistics. In many practical settings, the Wasserstein distance is an appropriate error metric for density estimation. For example, when estimating population densities in a geographic region, a small Wasserstein distance means that the estimate is able to capture roughly where the population mass is. In this work we study differentially private density estimation in the Wasserstein distance. We design and analyze instance-optimal algorithms for this problem that can adapt to easy instances.

Neural Information Processing Systems http://nips.cc/

We consider a Bayesian forecast aggregation model where n experts, after observing private signals about an unknown binary event, report th eir posterior beliefs about the event to a principal, who then aggregates the repor ts into a single prediction for the event. The signals of the experts and the outcome of the event follow a joint distribution that is unknown to the principal, but th e principal has access to i.i.d. "samples" from the distribution, where each sampl e is a tuple of the experts' reports (not signals) and the realization of the even t. Using these samples, the principal aims to find an ε -approximately optimal aggregator, where optimal-ity is measured in terms of the expected squared distance bet ween the aggregated prediction and the realization of the event.

Section 3 to take into account that the discussion on the asymptotic MMSE is now rigorous and not only heuristic.

In such a setting, distribution-free risk bounds are impossible, and the best one could hope for is a fully empirical data-dependent bound.

In such a setting, distribution-free risk bounds are impossible, and the best one could hope for is a fully empirical data-dependent bound.

Discrete distributions, particularly in high-dimensional deep models, are often highly multimodal due to inherent discontinuities. While gradient-based discrete sampling has proven effective, it is susceptible to becoming trapped in local modes due to the gradient information. To tackle this challenge, we propose an automatic cyclical scheduling, designed for efficient and accurate sampling in multimodal discrete distributions. Our method contains three key components: (1) a cyclical step size schedule where large steps discover new modes and small steps exploit each mode; (2) a cyclical balancing schedule, ensuring balanced proposals for given step sizes and high efficiency of the Markov chain; and (3) an automatic tuning scheme for adjusting the hyperparameters in the cyclical schedules, allowing adaptability across diverse datasets with minimal tuning. We prove the non-asymptotic convergence and inference guarantee for our method in general discrete distributions. Extensive experiments demonstrate the superiority of our method in sampling complex multimodal discrete distributions.

In modern machine learning, users often have to collaborate to learn distributions that generate the data. Communication can be a significant bottleneck. Prior work has studied homogeneous users---i.e., whose data follow the same discrete distribution---and has provided optimal communication-efficient methods. However, these methods rely heavily on homogeneity, and are less applicable in the common case when users' discrete distributions are heterogeneous. Here we consider a natural and tractable model of heterogeneity, where users' discrete distributions only vary sparsely, on a small number of entries. We propose a novel two-stage method named SHIFT: First, the users collaborate by communicating with the server to learn a central distribution; relying on methods from robust statistics. Then, the learned central distribution is fine-tuned to estimate the individual distributions of users. We show that our method is minimax optimal in our model of heterogeneity and under communication constraints. Further, we provide experimental results using both synthetic data and $n$-gram frequency estimation in the text domain, which corroborate its efficiency.